'''
next_map = {} 这是一个字典
next_map[2]=-1  对应的就是  next_map = {2:-1}

在处理 下一个最大元素的问题的时候，必须从右向左遍历，
因为如果从左往右遍历的话, 处理当前元素的时候，右边的信息还没有处理 无法知道 下个更大的元素到底是哪个 处理完全遍历完
从右往左便遍历的时候,在处理当前元素的时候 右边的信息已经处理过了 只需要比较 当前元素 和 处理过的元素即可，对于右边处理过的元素
    可以使用 单调栈来记录(单调栈：栈里面存的数字, 越上面越小)

在从右向左遍历的时候 如果当前元素比 栈顶的元素大 , 那么就弹出栈顶元素

先把 nums2 中下一个更大的元素找出来 借助单调栈 将下个最大元素组成 字典，在用 nums1 去 字典中查询

'''


def nextGreaterElement(self, nums1, nums2):
    ## 使用 单调栈处理 nums2
    stack = []
    next_map = {} ## 存储 nums2 中每个元素的下一个更大的元素
    
    ## 从右向左遍历 nums2
    for num in reversed(nums2):
        while stack and stack[-1]<= num: ## 维护单调栈 如果当前元素比 栈顶元素还大 果断丢弃栈顶元素 将当前元素压入栈中国
            stack.pop()
        ## 组成字典 栈顶元素就是当前元素的下一个最大元素 。如果此时栈顶没有 则默认为 -1
        next_map[num] = stack[-1] if stack else -1
        stack.append(num)
        
    ## 查询 nums1 在字典中的情况
    ## 直接将 nums1 中的元素 和 字典的可 作比较
    ans = []
    for i in nums1:
        ans.append(next_map[i])
        
    return ans
        
    
    
    
    
    
        
        
        
        
        
        
        
        
